package Classic150;

import LinkedList.ListNode;

public class 排序链表 {
    /*
        自顶向下归并排序，分 —> 合
     */
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        return mergeSort(head, null);
    }

    private ListNode mergeSort(ListNode head, ListNode tail) {
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode fast = head, slow = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) fast = fast.next;
        }
        ListNode leftList = mergeSort(head, slow);
        ListNode rightList = mergeSort(slow, tail);
        return merge(leftList, rightList);
    }

    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dHead = new ListNode();
        ListNode cur = dHead;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if (head1 != null) cur.next = head1;
        else if (head2 != null) cur.next = head2;
        return dHead.next;
    }
}
